package Data_Structure.Sort;

import java.util.Arrays;

/**
 * @className: HeapSort
 * @author: 芃
 * @description: 堆排序实现
 * @date: 2023/8/20 17:19
 */
//时间复杂度：建堆->O(N) 调整位置-》O(N*logN)  ---> O(N*logN)
//空间复杂度：O(1) 未开辟额外空间
//稳定性：不稳定的
public class HeapSort {
    public static void heapSort(int[] arr){
        createHeap(arr);
        //建完大根堆后，依次将堆顶的元素放到数组末尾
        int end = arr.length - 1;
        while (end > 0){
            //①交换0下标元素和数组末尾元素
            swap(arr,0,end);
            //②向下调整0下标这棵树->调整到end位置
            //为什么是end而不是end-1？
            //我们的第二个参数代表调整结束的位置，比如10个元素，此时end就等于9，参考shiftDown函数，调整到8位置就结束了，因此不需要-1
            shiftDown(arr,0,end);
            //③end--
            end--;
        }
    }

    /**
     * @param arr:
     * @param i:
     * @param j:
     * @author: zyp19
     * @description: 交换函数
     * @date: 2023/8/27 11:18
     */
    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * @param array:
     * @author: zyp19
     * @description: 建大根堆
     * @date: 2023/8/27 11:07
     */
    public static void createHeap(int[] array){
        int parent = (array.length - 2) / 2;
        for (int i = parent; i >= 0; i--) {
            shiftDown(array,i,array.length);
        }
    }

    /**
     * @param array: 数组
     * @param parent: 调整的树的根节点
     * @param len: 数组长度
     * @author: zyp19
     * @description: 向下调整-》每次调用该函数，只会调整传入的节点这棵树
     * @date: 2023/8/27 11:09
     */
    public static void shiftDown(int[] array,int parent,int len){
        int child = 2*parent+1;
        //1、最起码是有左孩子的，至少有一个孩子
        while (child < len){
            if (child + 1 < len && array[child] < array[child + 1]){
                child++;//child下标保证为当前树的左右孩子的最大值
            }
            //走到这，就找到了左右孩子的最大值
            if (array[child] > array[parent]){
                //交换
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
                //交换完成后，需要继续向下调整，保证左右子树依然是大根堆
                parent = child;
                child = 2*parent + 1;
            }else {
                //说明左右孩子最大值依然没有父节点的值大
                break;
            }
        }
    }
}
